Linguagem Regular:

 

 

Uma linguagem é regular se somente se ela é aceita por um autômato finito. Tomando um autômato finito M = (Q, å , d , s0, F) a:

        d *(s0, x) Ï F

 

Conjunto ou linguagem aceita por M:

L(M) = { x Î å * | d * (s0, x) Î F}

A Í å * é REGULAR se A = L(M) para algum autômato finito M, tal que L é uma linguagem regular.

 

Linguagem Livre de Contexto:

 

A linguagem L é livre de contexto se somente se existe uma gramática livre de contexto G tal que L = L(G).

Definição: Uma gramática G = <V,T,S,P> é livre de contexto se todas as produções em P tem a forma A® x, onde AÎ V e xÎ (VÈ T)*.

Obs: Toda linguagem regular é livre de contexto.

 

Linguagem Sensível ao Contexto:

Linguagens sensíveis ao contexto são geradas por gramáticas da seguinte forma: G = (V,T,P,S) onde as produções em P são da forma a ® b , com a e b sendo cadeias arbitrárias de símbolos da gramática, a ¹ e e b tem que ser pelo menos tão grande (longo) quanto a (| a | £ | b |).

O nome sensível ao contexto vem da forma normal para estas gramáticas onde cada produção tem a forma:

a 1Aa 2® a 1ba 2 com b ¹ e .

Isto é, a variável A pode ser substituída pela cadeia b somente no contexto a 1 _ a 2.

Obs: Quase todas as linguagens que trabalhamos são sensíveis ao contexto. As únicas provas que certas linguagens não são sensíveis ao contexto são baseadas em diagonalização.

 

Linguagem Recursivamente Enumerável:

Se L é uma linguagem recursivamente enumerável, então L = L(G) para alguma gramática G do tipo 0, e se, L é L(G) para uma gramática tipo 0 G = (V,T,P,S), então L é uma linguagem recursivamente enumerável (existe uma máquina de Turing para ela), ou seja, essas linguagens são geradas por gramáticas do tipo zero.

Gramáticas tipo 0 G = (V,T,P,S) onde as produçãos de P tem a forma

a ® b com a e b sendo cadeias arbitrárias de símbolos da gramática e e a ¹ e

 

 

.